package cn.edu.njust.alg.leetcode;


public class Leetcode_198_House_Robber {

	public static int rob(int[] nums) {
		if (nums.length <= 0) {
			return 0;
		} else if (nums.length == 1) {
			return nums[0];
		} else if (nums.length == 2) {
			return Math.max(nums[0], nums[1]);
		}
		int[] dp = new int[nums.length];
		int max = 0;
		int res = Math.max(nums[0], nums[1]);
		dp[0] = nums[0];
		dp[1] = nums[1];
		for (int i = 2; i < dp.length; i++) {
			max = Integer.MIN_VALUE;
			for (int j = 0; j < i - 1; j++) {
				if (dp[j] > max) {
					max = dp[j];
				}
			}
			dp[i] = max + nums[i];
			if (res < dp[i]) {
				res = dp[i];
			}
		}
		return res;
	}

	public static void main(String[] args) {

		int[] nums = { 1, 23, 4, 6, 7 };
		System.out.println(rob(nums));
	}

}
